{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Bad Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBadPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计坏数对的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从<strong>&nbsp;0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。如果 <code>i &lt; j</code>&nbsp;且&nbsp;<code>j - i != nums[j] - nums[i]</code>&nbsp;，那么我们称&nbsp;<code>(i, j)</code>&nbsp;是一个 <strong>坏</strong><strong>数对</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <code>nums</code>&nbsp;中 <strong>坏数对</strong>&nbsp;的总数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [4,1,3,3]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。\n",
    "数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。\n",
    "数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。\n",
    "数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。\n",
    "数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。\n",
    "总共有 5 个坏数对，所以我们返回 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,3,4,5]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>没有坏数对。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-bad-pairs](https://leetcode.cn/problems/count-number-of-bad-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-bad-pairs](https://leetcode.cn/problems/count-number-of-bad-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,3,3]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        # nums[j]+j == nums[i]+i\n",
    "        n = len(nums)\n",
    "        d = {}\n",
    "        ans = comb(n, 2)\n",
    "        for i in range(n):\n",
    "            ans -= d.get(-nums[i]+i, 0)\n",
    "            d[-nums[i]+i] = d.get(-nums[i]+i, 0) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        good_dict = {}\n",
    "        res = n * (n - 1) // 2\n",
    "        for i in range(len(nums)):\n",
    "            good_num = nums[i] - i\n",
    "            if good_num not in good_dict:\n",
    "                good_dict[good_num] = 0\n",
    "            good_dict[good_num] += 1\n",
    "        for key, value in good_dict.items():\n",
    "            res -= value * (value - 1) // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        c = Counter()\n",
    "        good = 0\n",
    "        for i in range(n):\n",
    "            c[nums[i] - i] += 1\n",
    "        for i in c.values():\n",
    "            good += (i - 1) * i // 2\n",
    "        return (n - 1) * n // 2 - good"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for i, x in enumerate(nums):\n",
    "            ans += i - cnt[x - i]\n",
    "            cnt[x - i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        s=math.comb(n,2)\n",
    "        c=Counter()\n",
    "        for i,num in enumerate(nums):\n",
    "            num-=i\n",
    "            c[num]+=1\n",
    "        g=0\n",
    "        for k in c.values():\n",
    "            g+=math.comb(k,2)\n",
    "        return s-g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        #copy 0x3\n",
    "        n,cnt = len(nums),Counter()\n",
    "        ans = n*(n-1)//2\n",
    "        for i , num in enumerate(nums):\n",
    "            ans -= cnt[num-i]\n",
    "            cnt[num-i] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        return comb(len(nums), 2) - sum(comb(v, 2) for v in Counter(x - i for i, x in enumerate(nums)).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter()\n",
    "        ans = n * (n - 1) // 2\n",
    "        for i,num in enumerate(nums):\n",
    "            ans -= cnt[num - i]\n",
    "            cnt[num - i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        ans = comb(n, 2)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans -= d[x-i]\n",
    "            d[x-i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n*(n-1)//2\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            ans -= cnt[nums[i]-i]\n",
    "            cnt[nums[i]-i] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        ans = 0\n",
    "        for index, num in enumerate(nums):\n",
    "            tmp = index - num\n",
    "            if tmp in dic:\n",
    "                val = dic[tmp]\n",
    "                ans += index - val\n",
    "                dic[tmp] += 1\n",
    "            else:\n",
    "                ans += index\n",
    "                dic[tmp] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x-i] += 1\n",
    "        n = len(nums)\n",
    "        ans = 0 \n",
    "        for v in d.values():\n",
    "            ans += v * (n - v)\n",
    "        return ans >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n*(n-1)//2\n",
    "        cnt = Counter()\n",
    "        for i,n in enumerate(nums):\n",
    "            ans -= cnt[n-i]\n",
    "            cnt[n-i] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        map_ = dict()\n",
    "        res = len(nums)*(len(nums)-1)//2\n",
    "        for i in range(len(nums)):\n",
    "            t = nums[i]-i\n",
    "            if t in map_:\n",
    "                res -= map_[t]\n",
    "            map_[t] = map_.get(t, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for v in Counter(i - v for i, v in enumerate(nums)).values():\n",
    "            n -= v\n",
    "            ans += v * n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        count = {}\n",
    "        for i,value in enumerate(nums):\n",
    "            if value-i not in count:\n",
    "                count[value-i] = 1\n",
    "            else:\n",
    "                count[value-i]=count[value-i]+1\n",
    "        \n",
    "        sum=0\n",
    "        for n in count.values():\n",
    "            sum+= n*(n-1)//2\n",
    "        \n",
    "        n = len(nums)\n",
    "        return n*(n-1)//2-sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            val = num - i\n",
    "            ans += i - cnt[val]\n",
    "            cnt[val] += 1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        mp = collections.defaultdict(int)\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            ans += i - mp.get(i - n, 0)\n",
    "            mp[i - n] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x-i] += 1\n",
    "        n = len(nums)\n",
    "        ans = 0 \n",
    "        for v in d.values():\n",
    "            ans += v * (n - v)\n",
    "        return ans >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            x -= i\n",
    "            ans += cnt[x]\n",
    "            cnt[x] += 1\n",
    "        return len(nums) * (len(nums) - 1) // 2 - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        n, m = len(nums), 0\n",
    "        for i, j in enumerate(nums):\n",
    "            if j - i in dic:\n",
    "                dic[j - i] += 1\n",
    "            else:\n",
    "                dic[j - i] = 1\n",
    "        for i in dic.values():\n",
    "            m += i * (i - 1) >> 1\n",
    "        return ((n * (n - 1)) >> 1) - m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n,cnt=len(nums),Counter()\n",
    "        ans=n*(n-1)//2\n",
    "        for i,num in enumerate(nums):\n",
    "            ans-=cnt[num-i]\n",
    "            cnt[num-i]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        ans = len(nums) * (len(nums) - 1) // 2\n",
    "        for i, x in enumerate(nums):\n",
    "            x -= i\n",
    "            ans -= cnt[x]\n",
    "            cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        # 构建一个 空Counter() 实例\n",
    "        # 之后就可以当作一个字典使用，有键值对的形式存储\n",
    "        n, count = len(nums), Counter()\n",
    "        res = n * (n - 1) // 2  # n个元素所有的数对数量是 n(n-1)/2\n",
    "        # 遍历数组nums及其下标\n",
    "        # 如果 (num-i) 在字典中，说明他是一个好数，那就用 总数-好数的数量\n",
    "        # 然后再给这个地方加上一个1，说明这个地方的好数数量又多了一个\n",
    "        for i, num in enumerate(nums):\n",
    "            res -= count[num - i]\n",
    "            count[num-i] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for i,num in enumerate(nums):\n",
    "            num -= i\n",
    "            ans += cnt[num]\n",
    "            cnt[num] += 1\n",
    "        tot = n*(n-1)//2\n",
    "        return tot-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        pre = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            ans += pre[nums[i]-i]\n",
    "            pre[nums[i]-i] += 1\n",
    "        return n*(n-1)//2 - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n * (n-1) // 2\n",
    "        cnt = Counter()\n",
    "        for i, num in enumerate(nums):\n",
    "            ans -= cnt[num - i]\n",
    "            cnt[num - i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        ans = comb(n, 2)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans -= d[x-i]\n",
    "            d[x-i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\r\n",
    "        # 要想不是坏数对，就必须保持按照1递增的规律增长\r\n",
    "        n = len(nums)\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        a = {}\r\n",
    "        for i in range(n):\r\n",
    "            tmp = nums[i] - i\r\n",
    "            if tmp in a:\r\n",
    "                a[tmp] += 1\r\n",
    "            else:\r\n",
    "                a[tmp] = 1\r\n",
    "        #print(a)\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "        ans = (n) * (n - 1) // 2\r\n",
    "\r\n",
    "        for kry, val in a.items():\r\n",
    "            if val > 1:\r\n",
    "                ans -= val * (val - 1) // 2\r\n",
    "            \r\n",
    "    \r\n",
    "\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        good_pair = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            good_pair += cnt[i-num]\n",
    "            cnt[i-num]+=1\n",
    "        n = len(nums)\n",
    "        total = n * (n - 1) // 2\n",
    "        return total - good_pair\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        table = Counter()\n",
    "        for i in range(n):\n",
    "            table[nums[i]-i] += 1\n",
    "        ans = 0\n",
    "        for c in table:\n",
    "            ans += (n-(table[c]))*table[c]\n",
    "        return ans//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        c, res = collections.Counter(), 0\n",
    "        for i in range(len(nums)):\n",
    "            res += c[nums[i]-i]\n",
    "            c[nums[i]-i] += 1\n",
    "        return len(nums)*(len(nums)-1)//2-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = defaultdict(int)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x - i] += 1\n",
    "        return n * (n-1) // 2 - sum(v * (v - 1) // 2 for v in d.values())\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = defaultdict(int)\n",
    "        ret = n * (n - 1) // 2\n",
    "        for i, x in enumerate(nums):\n",
    "            ret -= d[x - i]\n",
    "            d[x - i] += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = defaultdict(int)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x - i] += 1\n",
    "        return n * (n-1) // 2 - sum(v * (v - 1) // 2 for v in d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        s=math.comb(n,2)\n",
    "        c=Counter()\n",
    "        for i,num in enumerate(nums):\n",
    "            num-=i\n",
    "            c[num]+=1\n",
    "        g=0\n",
    "        for k in c.values():\n",
    "            g+=math.comb(k,2)\n",
    "        return s-g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = dict()\n",
    "        for i in range(n):\n",
    "            x = nums[i] - i\n",
    "            d[x] = d.get(x, 0) + 1\n",
    "        return n * (n - 1) // 2 - sum(x * (x - 1) // 2 for x in d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnts = Counter(i-nums[i] for i in range(n))\n",
    "        return n*(n-1)//2 - sum(i*(i-1)//2 for i in cnts.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        d = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        for pos, n in enumerate(nums):\n",
    "            k = n - pos\n",
    "            ans += pos - d[k]\n",
    "            d[k] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        counter = defaultdict(int)\n",
    "\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            res += i - counter[x - i]\n",
    "            counter[x - i] += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        hashmap= collections.Counter()\n",
    "        res=0\n",
    "        for i,x in enumerate(nums):\n",
    "            res+=i-hashmap[i-x]\n",
    "            hashmap[i-x]+=1\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "            下标从0 开始\n",
    "                j -i != nums[j] - nums[i] \n",
    "                移项 \n",
    "                j - nums[j]!= i -nums[i]\n",
    "            感觉像贡献法\n",
    "        \"\"\"\n",
    "        d = defaultdict(int)\n",
    "        for i,x in enumerate(nums):\n",
    "            d[i-x]+=1\n",
    "        s = len(nums) \n",
    "        ans = 0\n",
    "        print(d)\n",
    "        for val in d.values():\n",
    "            print(val,s-val)\n",
    "            ans += (s-val)*val\n",
    "\n",
    "        return ans//2\n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        mp,ans={},len(nums)*(len(nums)-1)//2\n",
    "        for i in range(0,len(nums)):\n",
    "            mp[nums[i]-i]=mp.get(nums[i]-i,0)+1\n",
    "            ans-=mp[nums[i]-i]-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n * (n - 1) // 2\n",
    "        cnt = Counter()\n",
    "        for i, x in enumerate(nums):\n",
    "            ans -= cnt[i - x]\n",
    "            cnt[i - x]+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "      n=len(nums)\n",
    "      arr={}\n",
    "      ans=0\n",
    "      for i in range(n):\n",
    "        x=nums[i]-i\n",
    "        if x in arr:\n",
    "          arr[x]+=1\n",
    "        else:\n",
    "          arr[x]=1\n",
    "      k=sum(arr.values())\n",
    "      for i in arr:\n",
    "        ans+=arr[i]*(k-arr[i])\n",
    "      return ans//2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        delta = [x - i for i, x in enumerate(nums)]\n",
    "        c = Counter(delta)\n",
    "        ans = 0\n",
    "        for k, v in c.items():\n",
    "            ans += v * (n - v)\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter([num-i for i, num in enumerate(nums)])\n",
    "        ans = n*(n-1)>>1\n",
    "        for cnt in cnt.values():\n",
    "            ans -= cnt * (cnt-1)>>1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n * (n - 1) // 2\n",
    "        cnt = Counter([nums[i] - i for i in range(n)])\n",
    "        for i in cnt.values():\n",
    "            ans -= i * (i - 1) // 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        d = Counter([x-i for i,x in enumerate(nums)])\n",
    "        return n*(n-1)//2 - sum(x*(x-1)//2 for x in d.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        x = []\n",
    "        dict = {}\n",
    "        for i in range(0,len(nums)):\n",
    "            x.append(i + 1 - nums[i])\n",
    "            if (i + 1 - nums[i]) in dict:\n",
    "                dict[i + 1 - nums[i]] += 1\n",
    "            else:\n",
    "                dict[i + 1 - nums[i]] = 1\n",
    "        ans = int(len(nums) * (len(nums) - 1) / 2)\n",
    "        for key in dict:\n",
    "            ans = ans - int((dict[key] * (dict[key] - 1)) / 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        x = []\n",
    "        dict = {}\n",
    "        for i in range(0,len(nums)):\n",
    "            x.append(i + 1 - nums[i])\n",
    "            if (i + 1 - nums[i]) in dict:\n",
    "                dict[i + 1 - nums[i]] += 1\n",
    "            else:\n",
    "                dict[i + 1 - nums[i]] = 1\n",
    "        ans = int(len(nums) * (len(nums) - 1) / 2)\n",
    "        for key in dict:\n",
    "            ans = ans - int((dict[key] * (dict[key] - 1)) / 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBadPairs(self, nums: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if(nums[i]-i not in mapping):\n",
    "                mapping[nums[i]-i] = 1\n",
    "            else:\n",
    "                mapping[nums[i]-i] += 1\n",
    "        arrs = list(mapping.items())\n",
    "        cur = 0\n",
    "        result = 0\n",
    "        for i in range(len(arrs)):\n",
    "            result += cur*arrs[i][1]\n",
    "            cur += arrs[i][1]\n",
    "        return result\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
